Following the advancement of 3D scanning devices, a significant amount of 3D points (frequently considered as point clouds) are obtained (e.g. 3D models of 3D mechanical parts or scans of the terrain). These point clouds are used directly (e.g. they are visualized by the point-based rendering approach) or a reconstruction process is applied to form a boundary representation of the scanned objects. In this case, topological relationships between scanned points are established leading to the polyhedral meshes. These polyhedral meshes are often triangular or quadrilateral.
3D meshes have a wide range of applications in entertainment (computer graphics, animation, virtual reality, visual effects (VFX)), science (visualization of various scientific data), engineering (design, manufacturing), and culture (digital heritage). For example, graphically rendered computer generated worlds in online games are almost completely made of 3D meshes that represent the surfaces of different entities. Transferring such data in reasonable time through the communication channels is generally solved by data compression.
Data compression represents the original data with fewer bits, in order to enable efficient storage and fast local or network-based transfer. This saves the storage space, transfer time and hardware costs. Binary data is usually compressed by either run-length or entropy encoding. The more common representatives of the latter are Huffman algorithm and arithmetic coding. Unfortunately, binary compression is not the most applicable form of compression when geometrical data is the input. For this, more sophisticated algorithms have been developed that decrease the information entropy by eliminating similarities within given data (e.g. similar regions in images), before applying binary compression.
The compression methods can be either lossless or lossy. In the latter case, a certain amount of original information loss is irreversibly introduced. These losses are acceptable only, if the human perception system still considers the data as acceptable (e.g. at compression of images, sounds, or videos, but not at text compression). Generally, the lossy compression yields better compression ratio, at the cost of lower quality. A good compromise is near-lossless compression, where the loss of quality is very small, while the compression ratio remains high. While the compression of images and videos has existed for a long time, the technological evolution of graphic hardware towards the end of the 20th century contributed to increasing demands for compression of 3D geometry—a relatively new subfield in data compression.
Various methods have been developed for the compression of 3D meshes and point clouds. Some of the first methods use variable length coding and delta-coding on individual vertices' positions. This was extended for out-of-core application by utilizing a mesh buffer. In an example of compressing and transmitting a 3D geometric model, geometric data is compressed either by the conventional Huffman coding or by the delta-coding. Another example compresses both the meshes' topology and the geometry. The former is encoded with constructive traversing over the dual-graph, while the latter is encoded by successive quantization and bit-plane arithmetic coding. Another example of a method includes compressing the regularly or irregularly tiled surfaces of 3D geometry by storing the differences of adjacent vertices. Another example of a method includes the compressions of geometric models by using spanning trees, where the data structure has a table of vertex runs, triangular runs, and zero or more marching records that define the connectivity. Another example of a method decomposes 3D objects into segments, where each segment's set of vertices is delta-coded and compressed using Huffman coding. Another example of a method includes a lossy compression of graphic data, where given models' faces are approximated by predetermined geometric shapes. Another example of a method includes the rewritable compression of triangulated data, where triangular stripes are identified from the neighboring triangles, and compressed using Huffman coding. Another example of a method includes a progressive geometry compression scheme based on semi-regular meshes that are used with wavelet transform, zero-tree coding, and subdivision-based reconstruction. Another example of a method includes a lossy compression scheme that quantizes extracted geometric primitives into integer values by using fixed grid. Another example of a method identifies regions of dominant valence and compresses a 3D model with reduced connectivity. Another example of a method includes a prediction scheme, where the spatial or dihedral angles between triangles are encoded relative to individual prediction triangles. The prediction residuals are then compressed with entropy or a range coder. Another example of a method includes 3D contents data encoding/decoding over its primitives by the use of predetermined encoding order consisting of quantization, predictive coding, and entropy coding. Another example of a method considers the compression of 3D meshes with repeated patterns, which are detected by clustering the scaling factors and orientation axes. The detected connected components are then quantized by using references to the clusters, and finally compressed with entropy encoding. Another example of a method includes a triangular mesh compression method that subsamples original data in order to generate low-resolution representation. Error values are calculated as the differences between the low resolution and original data. These are then thresholded and stored together with associated low resolution data. Another example of a method includes lossy 3D model compression, where the original 3D model is represented by 3D patches that are efficiently stored by using control points.
One of the compression methods for 3D meshes applies spectral methods to compress compact representation of 3D mesh data. They achieved this by projecting the mesh geometry onto an orthonormal basis that was derived from topological relations. Another example of a method includes segmenting 3D models using principal plane analysis. The obtained segments' geometry and topology are then compressed with triangle traversal scheme.
3D geometry can also be represented in the form of a huge amount of individual points, which do not have any topological relations. This is especially common in point clouds that are obtained using 3D laser-scanning technologies. Such collections of points are known as point clouds. An example of a method stores the point cloud into a 3D regular grid that is then rearranged into a 2D grid, where the data is compressed into the form of a gradient. Another example of a method includes a lossy point cloud compression method, where surfaces are constructed over the point cloud based on imposed error constraint. Then the surface is stored that requires a minimal amount of memory. Several methods are also specialized for the compression of LiDAR (Light Detection And Ranging) point cloud, which is a result for airborne-laser scanning (ALS) or mobile-laser scanning (MLS) in order to capture high-quality 3D representation of terrain, vegetation, and man-made objects. Of course, reconstruction algorithms can be used on point cloud and generate a 3D mesh in order to establish topology. The reconstructed mesh can be compressed with the aforementioned algorithms for 3D mesh compression. Another example of a method includes a predictive coding for single-rate compression of point cloud data. Another example of a method includes a progressive compression method based on octree decomposition of space and prediction schema. Another example of a method includes a technique for single-rate compression of point clouds by the use of a spanning tree within the prediction schema. Another example of a method uses iterative octree subdivision of the point cloud. At each subdivision, the authors approximate points' positions by the geometry centers of the octree nodes. Another point cloud compression method by using octree-based subdivison encodes the octree structure as well the equations of least-square-fitted planes within each octree node. Therefore, the given compression is lossy, as the original point cloud data is lost. For decompression, the authors firstly decode the octree and the plane equations, and then they reconstruct the 3D model.
Chain codes are one of the more efficient representations for 2D contours, edges, and rasterized binary shapes. They are generally used within the image processing field. Various chain code compression algorithms have been developed. Chain code lossless compression using move-to-front transform and adaptive run-length encoding presented a 3D chain code method for compressing 3D discrete curves (e.g. 3D geometric object's skeleton). They have also shown that 2D chain codes are applicable for lossy compression of 2D rasterized slices (i.e. cross sections) from a voxelized watertight 2.5D mesh (e.g. digital terrain model). Voxelization transforms 3D points into 3D regular grid consisting of equally large cells called voxels (analogous to 2D pixels in images) that contain a scalar value. Such cross sections can be directly encoded with 2D chain codes. However, this scheme is not applicable for the compression of non-watertight 3D meshes or watertight 3D meshes, which consist of multiple separated segments with variable thicknesses. This can be addressed with voxelized watertight models by using a 3D chain code over Hamiltonian cycle of the voxels' graph. Since, the construction of such cycle is NP-complete, it is not suitable for larger datasets that are used in practice.